/*
Given an integer (assume it's smaller than 50), write an algorithm that will generate all possible combinations of integers greater than 1 and they produce a sum equals to this number. The same number can appear more than once in a combination. What's the time complexity of your algorithm?

For example: 
<=1 -> {}
2 -> {2}, 
3->{3}, 
4->{[4], [2, 2]}, 
5->{[5], [3, 2]}, 
6->{[6], [4, 2], [3, 3], [2, 2, 2]} 
7->{[7], [5, 2], [4, 3], [3, 2, 2]}
8->{[8], [6, 2], [5, 3], [4, 4], [4, 2, 2], [3, 3, 2], [2, 2, 2, 2]}
*/

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void getCombin(int index, int target, vector<int> cur, vector<vector<int> > &ans)
{
    if (target == 0) {
	ans.push_back(cur);
	return;	
    }

    for (int i = index; i <= target; i++) {
	cur.push_back(i);
	getCombin(i, target-i, cur, ans);
	cur.pop_back();
    }
}

int main(int argc, char **argv)
{
	vector<vector<int> > ans;
        vector<int> cur;
        getCombin(2, 2, cur, ans);
	for (int i = 0; i < ans.size(); i++) {
	    for (int j = 0; j < ans[i].size(); j++)
		cout << ans[i][j] << " ";
	    cout << endl;
	}
}
